//
// Created by wangxiyue on 2019/8/16.
//
#include <stdio.h>

/**
 * 当n=44的时候，超出时间限制
 * @param n 第n层台阶
 * @return
 */
int climbStairs(int n) {
    if (n <= 0) {
        return 1;
    }
    return n <= 2 ? n : climbStairs(n - 1) + climbStairs(n - 2);
}

int climbStairs2(int n) {
    long a[n+1];
    a[0] = 1l;
    a[1] = 1l;
    for(int i=2;i<=n;i++){
        a[i] = a[i-1] + a[i-2];
    }
    return a[n];
}

int main() {
//    printf("%d\n",climbStairs(2));
//    printf("%d\n",climbStairs(3));
//    printf("%d\n",climbStairs(0));
    for (int i = 0; i < 100; ++i) {
        printf("%d\n", climbStairs2(i));
    }
//    printf("%d\n",climbStairs(1000000));
    return 0;
}